/*
class Solution {
public:
    vector<vector<int>>s;
    bool st[10];
    vector<vector<int>> permute(vector<int>& nums) {
        s = dfs(0, nums);
        return s;
    }
    vector<vector<int>> dfs(int x, vector<int> nums)
    {
        int n = nums.size();
        if (x == n - 1)
        {
            s.push_back(nums);
            return s;
        }
        for (int i = x; i < n; i ++)
        {
            swap(nums[i], nums[x]);
            dfs(x + 1, nums);
            swap(nums[x], nums[i]);
        }
        return s;
    }
};
*/

/*
#include<bits/stdc++.h>
using namespace std;
const int N = 20;
bool udg[N], dg[N], col[N];
int n;
char g[N][N];
void dfs(int x)
{
    if (x == n)
    {
        for(int i = 0; i < n; i ++)
        {
            cout << g[i] << endl;
        }
        cout << endl;
        return;
    }
    for (int i = 0; i < n; i ++)
    {
        if (!dg[i + x] && !udg[n + i - x] && !col[i])
        {
            dg[i + x] = udg[n + i - x] = col[i] = true;
            g[x][i] = 'Q';
            dfs(x + 1);
            dg[i + x] = udg[n + i - x] = col[i] = false;
            g[x][i] = '.';            
        }
    }
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
    {
        for (int j = 0; j < n; j ++)
        {
            g[i][j] = '.';
        }
    }
    dfs(0);
    return 0;
}
*/
/*
#include<bits/stdc++.h>
using namespace std;
int res = 0;
bool col[5], udg[5], dg[5];
int n;
int g[5][5]
int cnt1, cnt2;
void dfs(int x)
{
  if (x == n)
  {
    res ++;
  }
  for (int i = 0; i < n; i ++)
  {
    if ()
  }
}
int main()
{
  n = 5;
  cnt1 = cnt2 = 0;
  for(int i = 0; i < n; i ++)
  {
    for (int j = 0; j < n; j ++)
    {
      g[i][j] = 0;
    }
  }
  dfs(0);
  return 0;
}
*/




































